// 不同路径

package Leetcode;

class solution_062 {
    public static int[] result = new int[1];

    public static int uniquePaths(int m, int n) {
        int currentX = 1;
        int currentY = 1;
        backTrack(result, m, n, currentX, currentY);
        return result[0];
    }

    public static void backTrack(int[] result, int m, int n, int currentX, int currentY) {
        if (currentX == m && currentY == n) {
            result[0]++;
            return;
        }
        if (currentX > m || currentY > n)
            return;
        if (currentX < m) {
            backTrack(result, m, n, currentX + 1, currentY);
        }
        if (currentY < n) {
            backTrack(result, m, n, currentX, currentY + 1);
        }
    }

    public static void main(String[] args) {
        int m = 3;
        int n = 7;
        System.out.println(uniquePaths(m, n));
    }
}

public class Solution062 {
    public int uniquePaths(int m, int n) {
        // dp[i][j]表示到达(i,j)的路径个数
        int[][] dp = new int[m][n];
        // 初始化，左边界和上边界都是1
        for (int i = 0; i < m; i++)
            dp[i][0] = 1;
        for (int j = 0; j < n; j++)
            dp[0][j] = 1;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        return dp[m - 1][n - 1];
    }
}
